// https://leetcode-cn.com/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode-solution/

class Solution
{
public:
  int countSubstrings(string s) {
  {
    int count = 0; // 统计回文子串的个数

    int len = s.length();

    if (len < 1)
      return nullptr;

    vector<vector<int>> dp(len, vector<int>(len));

    for (size_t i = 0; i < len; i++)
      dp[i][i] = 1;

    int max_len = 1;
    int start = 0;
    for (int j = 1; j < len; j++)
    {
      for (int i = 0; i < (len - 1) && i < j; i++)
      {
        if (s[i] != s[j])
        {
          dp[i][j] = 0;
        }
        else
        {
          if (j - 1 <= 3)
          {
            dp[i][j] = 1;
          }
          else
          {
            dp[i][j] = dp[i + 1][j - 1];
          }
        }

        if (dp[i][j] && ((j - i + 1) > max_len))
        {
          count += 1; // 回文子串总数 + 1

          max_len = j - i + 1;
          start = i;
        }
      }
    }

    return count;
  }
};